﻿// See https://aka.ms/new-console-template for more information
//插入排序是一种简单的排序算法，他的工作原理与手动整理一副牌的过程非常相似。
//具体来说，我们在未排序区间选择一个基准元素，将该元素与其左侧已排序区间的元素逐一比较大小，并将该元素插入到正确的位置。
//插入排序的整体流程如下
//1.初始状态下，数组的第一个元素已经完成排序。
//2.选取数组的第二个元素作为base，将其插入到正确位置后，数组的前两个元素已排序
//3.选取第三个元素作为base，将其插入到正确位置后，数组的前三个元素已排序。
//4.以此类推，在最后一轮中，选取最后一个元素作为base，将其插入到正确位置后，所有元素均已排序

int[] nums=new int[5] { 55,11,32,84,21};
InsertionSort(nums);
foreach(int n in nums)
{
    Console.WriteLine(n);
}

Console.WriteLine("Hello, World!");

void InsertionSort(int[] nums)
{
    //外循环，已排序的元素数量微1，2，....，n
    for (int i = 1; i < nums.Length; i++)
    {
        int bas = nums[i], j = i - 1;
        //内循环，将bas插入到已排序部分的正确位置
        while (j >= 0 && nums[j] > bas)
        {
            nums[j + 1] = nums[j];//将nums[j]向右移动一位
            j--;
        }
        nums[j + 1] = bas;//将bas赋值到正确位置
    }
}